package LinkedList;

import java.util.Scanner;
import java.util.Stack;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //测试一把
        HeroNode hero1 = new HeroNode(1,"亚信","第一场");
        HeroNode hero2 = new HeroNode(2,"华讯","第二场");
        HeroNode hero3 = new HeroNode(3,"富士通","第三场");
        HeroNode hero4 = new HeroNode(4,"绿盟","第四场");
        HeroNode hero5 = new HeroNode(5,"字节跳动","第五场");
        HeroNode hero6 = new HeroNode(6,"烽火星空","第六场");

        //创建链表
        SingleLinkList singleLinkList = new SingleLinkList();
        singleLinkList.add(hero1);
        singleLinkList.add(hero2);
        singleLinkList.add(hero3);

        singleLinkList.addByOrder(hero6);
        singleLinkList.addByOrder(hero4);
        //singleLinkList.addByOrder(hero3);

        //显示一把
        singleLinkList.list();


        //测试修改
        HeroNode hero7 = new HeroNode(2,"科大讯飞","聊得挺好还是黄了！！！");

        singleLinkList.update(hero7);
        System.out.println("修改后");
        singleLinkList.list();
        System.out.println("删除后");
        singleLinkList.del(2);
        singleLinkList.list();

        System.out.println("笔试题  统计有效数据个数");
        System.out.printf("改链表中有 %d 个有效数据",singleLinkList.getLength(singleLinkList));

        /*System.out.println("请输入index");
        Scanner scanner = new Scanner(System.in);
        int index = scanner.nextInt();
        HeroNode lastIndexNode = singleLinkList.findLastIndexNode(singleLinkList.getHead(), index);
        System.out.println(lastIndexNode);*/
        //反转
        singleLinkList.reverseList(singleLinkList.getHead());
        System.out.println("反转后的链表~~");
        singleLinkList.list();

        System.out.println("使用栈实现反转打印");
        singleLinkList.reversePrint(singleLinkList.getHead());

        System.out.println("使用栈实现反转链表");
        singleLinkList.reversePrintByStack(singleLinkList.getHead());
        singleLinkList.list();
    }
}
class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;//指向下一个节点

    //构造器
    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode[no="+no+",name="+name+",nickname"+nickname+"]";
    }
}
//定义链表
class SingleLinkList{
    //先初始化一个头节点，头结点不要动，不存放具体的数据
    private HeroNode head = new HeroNode(0,"","");

    public HeroNode getHead() {
        return head;
    }

    //添加节点到单向链表
    //思路，当不考虑编号顺序时
    //1.找到当前链表的最后节点
    //2.将最后这个节点的next指向新的节点
    public void add(HeroNode heroNode){
        //因为head 节点不能动，因此指向新的节点
        HeroNode temp = head;
        //遍历链表，找到最后
        while(true){
            //找到链表的最后
            if (temp.next == null){
                break;
            }
            //如果没有找到最后，将temp后移
            temp = temp.next;
        }
        //当退出循环的时候,temp就指向了链表的最后
        temp.next = heroNode;
    }

    //第二种插入根据排名（no）插入
    public void addByOrder(HeroNode heroNode){
        HeroNode temp = head;
        boolean flag = false;//添加的节点是否已存在
        while(true){
            if (temp.next == null){//说明temp已经到链表最后
                break;
            }
            if (temp.next.no > heroNode.no){//位置找到就插在temp的后面
                break;
            }else if (temp.next.no == heroNode.no){//说明希望添加的heroNode的编号已经存在
                flag = true;
                break;
            }
            temp = temp.next;//后移，相当于遍历当前链表
        }
        //判断flag的值
        if (flag){
            System.out.printf("准备添加的英雄的编号 %d 已经存在，无法添加\n",heroNode.no);
        }else {
            //插入到链表中去
            System.out.printf("插入节点 %d \n",heroNode.no);
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }
    //修改节点的信息，根据编号来修改，即no不能修改
    public void update(HeroNode newheroNode){
        //判断是否为空
        if (head.next == null){
            System.out.println("链表为空~~");
            return;
        }
        //找到要修改的那个节点
        HeroNode temp = head.next;
        boolean flag = false;//表示是否找到此节点
        while(true){
            if (temp == null){
                break;//已经遍历完链表
            }
            if (temp.no == newheroNode.no){
                //找到了改节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag确定是否找到了要修改的节点
        if (flag){
            temp.name = newheroNode.name;
            temp.nickname = newheroNode.nickname;
        }else {
            System.out.printf("编号 %d 的英雄没有找到，不能修改",newheroNode.no);
        }
    }

    //删除节点
    /**
     * 思路
     * 1.head不能动 用temp变量找到改节点的前一个节点
     * 2.比较时是temp,next.no  和  将删除的节点no 比较
     */
    public void del(int no){
        HeroNode temp = head;
        boolean flag = false;
        while (true){
            if (temp.next == null){
                break;//到最后了
            }
            if (temp.next.no == no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.next = temp.next.next;
        }else {
            System.out.printf("要删除的 %d 节点不存在\n" ,no);
        }
    }
    /**
     * 遍历链表
     */
    public void  list(){
        //判断是否为空
        if (head.next == null){
            System.out.println("链表为空~~");
            return;
        }
        HeroNode temp = head;
        while (true){
            System.out.println(temp);
            if (temp.next == null){
                break;//到最后了
            }
            temp = temp.next;
        }
    }
    /**
     * 统计有效数据个数
     */
    public static int getLength(SingleLinkList singleLinkList){
        HeroNode head = singleLinkList.head;
        if (head.next == null){
            return 0;
        }
        int length = 0;
        HeroNode temp = head.next;//让我们跳过那个不是有效数据的头节点吧
        while (true){
            if (temp == null){
                break;
            }else {
                length++;
            }
            temp = temp.next;
        }
        return length;
    }
    /**
     * 查找单链表中倒数第K个节点
     * 思路：
     * 1.编写一个方法接受head节点，同时接受一个index
     * 2.index表示是倒数第index个节点
     * 3.先把链表从头到尾遍历一遍，得到有效数据的个数
     * 4.得到size后,在遍历一次  第size-index 就是倒数第index个数据
     */
    public HeroNode findLastIndexNode(HeroNode head, int index){
        //判断如果链表为空，返回null
        if (head.next == null){
            return  null;
        }
        int size = this.getLength(this);
        //第二次遍历到第size - index 个数据
        //先做一个index的校验
        if (index <= 0|| index>size){
            return null;
        }
        HeroNode temp = this.head;
        for (int i = 0; i <= (size - index); i++) {
            temp = temp.next;
        }
        return temp;
    }
    /**
     * 反转链表
     */
    public void reverseList(HeroNode head){
        if (head.next == null || head.next.next == null){
            return;
        }

        HeroNode cur = head.next;
        HeroNode next = null;
        HeroNode reverseHead = new HeroNode(0,"","");
        //遍历原来的链表，每遍历一个节点，就将其取出,并放在新的链表的最前边
        while (cur != null){
            next = cur.next;//先暂时保存当前节点的下一个节点，因为后边需要使用
            cur.next = reverseHead.next;//将cur的下一个节点指向行的链表的最前端
            reverseHead.next = cur;//将cur 连接到新的链表上
            cur = next;//让cur后移
        }
        //将head,next 指向 reverseHead.next 实现单链表的反转
        head.next = reverseHead.next;
    }
    /**
     * 反转打印（逆序打印）
     */
    public void reversePrint(HeroNode head){
        if (head.next == null){
            return;
        }
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;
        while(cur!= null){
            stack.add(cur);
            cur = cur.next;
        }
        //遍历栈
        while(stack.size()>0){
            System.out.println(stack.pop());
        }
    }
    /**
     * 反转链表（栈实现）
     *
     */
    public void reversePrintByStack(HeroNode head){
        if (head.next == null){
            return;
        }
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;
        while(cur!= null){
            stack.add(cur);
            cur = cur.next;
        }
        //遍历栈

        HeroNode newLinkList = new HeroNode(0,"","");
        HeroNode temp = newLinkList;
        while(stack.size()>0){
            HeroNode pop = stack.pop();
            while (true){
                if (temp.next == null){
                    break;
                }
                temp = temp.next;
            }
            pop.next = null;
            temp.next = pop;

        }
        head.next = newLinkList.next;
    }
}
